package offer;

import java.util.PriorityQueue;

class MedianFinder {
    PriorityQueue<Integer> min, max;

    /**
     * initialize your data structure here.
     */
    public MedianFinder() {
        min = new PriorityQueue<>();
        max = new PriorityQueue<>((a, b) -> b - a);
    }

    public void addNum(int num) {
        if (max.isEmpty() || num <= max.peek()) {
            max.offer(num);
            if (max.size() > min.size() + 1) {
                min.offer(max.poll());
            }
        } else {
            min.offer(num);
            if (min.size() > max.size()) {
                max.offer(min.poll());
            }
        }
    }

    public double findMedian() {
        if (max.size() > min.size()) {
            return max.peek();
        } else {
            return ((double) max.peek() + min.peek()) / 2;
        }
    }
}
